# class Solution:
#     def calc(self,se):
#         return se[0]*(len(se)-2)-sum(se[1:-1])
#     def trap(self, height) -> int:
#         stack=[]
#         seq=[]
#         for i in range(len(height)):
#             if len(stack)==0:
#                 stack.append(height[i])
#             elif height[i]>=stack[0]:
#                 stack.append(stack[0])
#                 seq.append(stack)
#                 stack=[height[i]]
#             else:
#                 stack.append(height[i])
#         length=len(stack)+1
#         stack=[]
#         for i in range(len(height)-1,len(height)-length,-1):
#             if len(stack)==0:
#                 stack.append(height[i])
#             elif height[i]>=stack[0]:
#                 stack.append(stack[0])
#                 seq.append(stack)
#                 stack=[height[i]]
#             else:
#                 stack.append(height[i])
#         return sum([self.calc(se) for se in seq])

# s=Solution()
# print(s.trap([0,1,0,2,1,0,1,3,2,1,2,1]))
class Solution:
    def calc(self,se):
        return se[0]*(len(se)-2)-sum(se[1:-1])
    def trap(self, height) -> int:
        stack=[]
        #seq=[]
        result=0
        for i in range(len(height)):
            if len(stack)==0:
                stack.append(height[i])
            elif height[i]>=stack[0]:
                stack.append(stack[0])
                result+=self.calc(stack)
                #seq.append(stack)
                stack=[height[i]]
            else:
                stack.append(height[i])
        length=len(stack)+1
        stack=[]
        for i in range(len(height)-1,len(height)-length,-1):
            if len(stack)==0:
                stack.append(height[i])
            elif height[i]>=stack[0]:
                stack.append(stack[0])
                result+=self.calc(stack)
                #seq.append(stack)
                stack=[height[i]]
            else:
                stack.append(height[i])
        return result


class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0
        n=len(height)
        left=[0]*n
        left[0]=height[0]
        right=[0]*n
        right[-1]=height[-1]
        for i in range(1,n):
            left[i]=max(left[i-1],height[i])
            right[n-i-1]=max(height[n-i-1],right[n-i])
        ret=0
        for i in range(1,n-1):
            a=min(left[i],right[i])-height[i]
            if a>0:
                ret+=a
        return ret

# 执行用时：
# 44 ms
# , 在所有 Python3 提交中击败了
# 79.95%
# 的用户
# 内存消耗：
# 15 MB
# , 在所有 Python3 提交中击败了
# 85.49%
# 的用户